//给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 
//
// 示例 1: 
//
// 输入: [2,3,-2,4]
//输出: 6
//解释:子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 输入: [-2,0,-1]
//输出: 0
//解释:结果不能为 2, 因为 [-2,-1] 不是子数组。
// Related Topics 数组 动态规划 👍 1250 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：乘积最大子数组
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P152_MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new P152_MaximumProductSubarray().new Solution();
//        int[] nums = MyUtil.createArray(2, 3, -2, 4);
        int[] nums = MyUtil.createArray(-1, 0, -2);
        MyUtil.print(solution.maxProduct(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 注意子数组可以仅自己一个
     * T: O(N)
     * S: O(1)
     */
    class Solution {
        public int maxProduct(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int maxF = nums[0], minF = nums[0], ans = nums[0];
            for (int i = 1; i < nums.length; i++) {
                int max = maxF, min = minF;
                maxF = Math.max(max * nums[i], Math.max(nums[i], min * nums[i]));
                minF = Math.min(min * nums[i], Math.min(nums[i], max * nums[i]));
                ans = Math.max(maxF, ans);
            }
            return ans;
        }
    }

//    class Solution {
//        public int maxProduct(int[] nums) {
//            if (nums == null || nums.length == 0) {
//                return 0;
//            }
//            if(nums.length == 1) {
//                return nums[0];
//            }
//            // 保存前缀积
//            TreeSet<Integer> set = new TreeSet<>();
//            set.add(1);
//            int res = 0;
//            int mult = 1;
//            for (int i = 0; i < nums.length; i++) {
//                if (nums[i] == 0) {
//                    mult = 1;
//                    set.clear();
//                    set.add(1);
//                    continue;
//                }
//                mult *= nums[i];
//                // 大于0离0最近的
//                Integer higher = set.higher(0);
//                if (higher != null) {
//                    res = Math.max(res, mult / higher);
//                }
//                // 小于0离0最近的
//                Integer lower = set.lower(0);
//                if (lower != null) {
//                    res = Math.max(res, mult / lower);
//                }
//
//                set.add(mult);
//            }
//
//            return res;
//        }
//    }

    //leetcode submit region end(Prohibit modification and deletion)

}